tg-me.com/golang_interview/1026
Create:
Last Update:
Last Update:
В этой задаче Вам необходимо найти самую длинную подстроку строки \(s\), такую что каждая буква в ней встречается не менее \(k\) раз. Если такой подстроки нет, вернуть 0.
Пример:
Вход: s = "aaabb", k = 3
Выход: 3
Объяснение: Самая длинная подходящая подстрока – "aaa", так как буква 'a' повторяется три раза.
### Описание алгоритма:
1. Генерация подстрок: Генерируем все возможные подстроки строки \(s\). Для каждой подстроки будем отслеживать частоту появления символов при помощи массива countMap.
2. Проверка валидности: Метод isValid проверяет, что каждый символ в текущей подстроке появляется хотя бы \(k\) раз. Это делается через проверку значений в массиве countMap. Если все символы удовлетворяют условию, то подстрока считается допустимой.
3. Обновление результата: Отслеживаем максимальную длину допустимых подстрок. Когда находим новую подходящую подстроку большей длины, обновляем результат. В итоге возвращаем длину самой длинной найденной подстроки.
Ответ:
package main
import (
"fmt"
)
func longestSubstring(s string, k int) int {
if len(s) == 0 || k > len(s) {
return 0
}
n := len(s)
result := 0
for start := 0; start < n; start++ {
countMap := make([]int, 26)
for end := start; end < n; end++ {
countMap[s[end]-'a']++
if isValid(countMap, k) {
if end-start+1 > result {
result = end - start + 1
}
}
}
}
return result
}
func isValid(countMap []int, k int) bool {
countLetters, countAtLeastK := 0, 0
for _, count := range countMap {
if count > 0 {
countLetters++
}
if count >= k {
countAtLeastK++
}
}
return countLetters == countAtLeastK
}
func main() {
fmt.Println(longestSubstring("aaabb", 3)) // Output: 3
fmt.Println(longestSubstring("ababbc", 2)) // Output: 5
}
@golang_interview